//和为k的子数组
class Solution {
    public:
        int subarraySum(vector<int>& nums, int k) {
            int n = nums.size();
            int cnt = 0;
            for(int i = 0; i < n; i++)
            {
                int sum = 0;
                for(int j = i; j < n; j++)
                {
                    sum += nums[j];
                    if(sum == k)
                    {
                        cnt++;
                    }
                }
            }
            return cnt;
        }
    };

    class Solution {
        public:
            int subarraySum(vector<int>& nums, int k) {
                int n = nums.size();
                unordered_map<int,int> hash;
                hash[0] = 1;
                int sum = 0;
                int cnt = 0;
                for(int i = 0; i < n; i++)
                {
                    sum += nums[i];
                    if(hash.count(sum - k) > 0)
                    {
                        cnt += hash[sum - k];
                    }
                    hash[sum]++;
        
                }
                return cnt;
            }
        };